public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] arr = new int[][]{{0,0,0}, {0,1,0}, {0,0,0}};
        System.out.println(s.uniquePathsWithObstacles(arr));
    }

    public int uniquePathsWithObstacles(int[][] ob) {
        /**
         * 不同路径Ⅱ*/
        // 1 预处理
        int m = ob.length;
        int n = ob[0].length;
        // 2 创建dp表（多创建一行、一列）
        int[][] dp = new int[m+1][n+1];
        // 3 初始化
        dp[1][0] = 1;
        // 4 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // 当不为障碍物时才计算路径和
                if(ob[i-1][j-1] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        // 5 返回值
        return dp[m][n];
    }
}
